import java.util.Stack;

public class bibtwork3 {
    //236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q){
            return root;
        }
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        findlux(root,p,stack1);
        findlux(root,q,stack2);
        int sum1=stack1.size();
        int sum2=stack2.size();
        if(sum1>sum2){
            int sum=sum1-sum2;
            while(sum!=0){
                sum--;
                stack1.pop();
            }
        }
        else{
            int sum=sum2-sum1;
            while(sum!=0&&!stack2.isEmpty()){
                sum--;
                stack2.pop();
            }
        }
        while(!stack1.isEmpty()&&!stack2.isEmpty()){
            TreeNode val1=stack1.pop();
            TreeNode val2=stack2.pop();
            if(val1==val2){
                return val1;
            }
        }
        return null;
    }
    public boolean findlux(TreeNode root, TreeNode index, Stack<TreeNode> stack){
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==index){

            return true;
        }
        boolean fleft= findlux(root.left,index,stack);
        if(fleft){
            return true;
        }
        boolean fright= findlux(root.right,index,stack);
        if(fright){
            return true;
        }
        stack.pop();//走到这里没有找到是这一条链没有找到 所以pop除去一个 返回上一个，继续向右边找（非常关键）
        return false;
    }
}
